The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(0(1(x1))) → 2(0(3(3(0(1(x1))))))
0(1(0(x1))) → 0(1(3(4(0(3(x1))))))
0(1(0(x1))) → 2(0(3(0(1(4(x1))))))
0(1(1(x1))) → 0(3(1(3(1(x1)))))
0(1(1(x1))) → 1(3(0(1(4(x1)))))
0(1(1(x1))) → 0(1(3(1(3(1(x1))))))
0(1(1(x1))) → 1(3(2(1(3(0(x1))))))
0(1(1(x1))) → 1(3(3(1(4(0(x1))))))
0(1(1(x1))) → 3(0(3(1(5(1(x1))))))
0(1(1(x1))) → 5(0(3(1(5(1(x1))))))
0(5(0(x1))) → 3(0(3(5(0(x1)))))
0(5(0(x1))) → 3(5(0(0(3(x1)))))
0(5(0(x1))) → 5(0(3(0(2(x1)))))
0(5(0(x1))) → 5(0(3(3(0(x1)))))
0(5(0(x1))) → 4(5(0(3(3(0(x1))))))
0(5(0(x1))) → 4(5(0(3(5(0(x1))))))
0(5(0(x1))) → 5(3(0(1(3(0(x1))))))
2(0(0(x1))) → 0(3(0(3(2(x1)))))
2(0(0(x1))) → 0(3(3(0(2(3(x1))))))
2(0(0(x1))) → 0(3(5(2(0(3(x1))))))
5(1(0(x1))) → 3(5(0(1(4(3(x1))))))
5(1(0(x1))) → 3(5(1(4(0(3(x1))))))
5(1(1(x1))) → 3(1(5(1(x1))))
5(1(1(x1))) → 1(3(1(3(5(x1)))))
5(1(1(x1))) → 1(3(3(3(5(1(x1))))))
5(1(1(x1))) → 1(3(5(5(1(4(x1))))))
0(2(0(1(x1)))) → 0(2(3(3(0(1(x1))))))
0(5(1(0(x1)))) → 0(0(1(3(5(x1)))))
0(5(4(0(x1)))) → 0(4(5(0(3(x1)))))
2(0(2(0(x1)))) → 3(0(3(0(2(2(x1))))))
2(0(4(1(x1)))) → 2(3(0(1(4(4(x1))))))
2(0(5(0(x1)))) → 0(0(3(5(2(x1)))))
2(2(4(1(x1)))) → 3(2(4(3(2(1(x1))))))
5(1(0(1(x1)))) → 0(5(1(4(3(1(x1))))))
5(1(1(0(x1)))) → 0(5(1(5(1(x1)))))
5(1(2(0(x1)))) → 3(1(3(5(0(2(x1))))))
5(1(5(0(x1)))) → 5(3(5(0(1(x1)))))
5(2(0(1(x1)))) → 5(1(0(3(2(x1)))))
5(3(1(1(x1)))) → 5(3(1(3(1(5(x1))))))
5(4(1(1(x1)))) → 5(1(4(1(4(5(x1))))))
5(5(1(0(x1)))) → 5(0(5(1(3(x1)))))
5(5(1(1(x1)))) → 5(1(3(5(0(1(x1))))))
0(2(4(1(0(x1))))) → 2(4(0(0(1(3(x1))))))
0(5(5(1(1(x1))))) → 5(1(3(5(0(1(x1))))))
2(2(2(4(1(x1))))) → 1(2(2(1(4(2(x1))))))
2(5(0(1(1(x1))))) → 5(1(2(0(1(3(x1))))))
5(0(2(4(1(x1))))) → 5(1(4(0(3(2(x1))))))
5(2(4(1(0(x1))))) → 0(2(3(4(5(1(x1))))))
5(3(0(4(1(x1))))) → 5(3(0(1(4(1(x1))))))
5(3(4(1(1(x1))))) → 1(4(3(5(2(1(x1))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1.
The certificate found is represented by the following graph.

Start state: 4061
Accept states: [4062, 4063, 4064]
Transitions:
4061→4062[0_1|0]
4061→4063[2_1|0]
4061→4064[5_1|0]
4061→4061[1_1|0, 3_1|0, 4_1|0]
4061→4065[1_1|1]
4061→4069[4_1|1]
4061→4073[1_1|1]
4061→4078[0_1|1]
4061→4083[0_1|1]
4061→4088[1_1|1]
4061→4093[1_1|1]
4061→4098[1_1|1]
4061→4101[5_1|1]
4061→4105[1_1|1]
4061→4110[4_1|1]
4061→4115[5_1|1]
4061→4120[5_1|1]
4061→4125[1_1|1]
4065→4066[3_1|1]
4066→4067[1_1|1]
4067→4068[3_1|1]
4068→4062[0_1|1]
4068→4078[0_1|1]
4068→4083[0_1|1]
4069→4070[1_1|1]
4070→4071[0_1|1]
4071→4072[3_1|1]
4072→4062[1_1|1]
4072→4078[1_1|1]
4072→4083[1_1|1]
4073→4074[3_1|1]
4074→4075[1_1|1]
4075→4076[3_1|1]
4076→4077[1_1|1]
4077→4062[0_1|1]
4077→4078[0_1|1]
4077→4083[0_1|1]
4078→4079[3_1|1]
4079→4080[1_1|1]
4080→4081[2_1|1]
4081→4082[3_1|1]
4082→4062[1_1|1]
4082→4078[1_1|1]
4082→4083[1_1|1]
4083→4084[4_1|1]
4084→4085[1_1|1]
4085→4086[3_1|1]
4086→4087[3_1|1]
4087→4062[1_1|1]
4087→4078[1_1|1]
4087→4083[1_1|1]
4088→4089[5_1|1]
4089→4090[1_1|1]
4090→4091[3_1|1]
4091→4092[0_1|1]
4092→4062[3_1|1]
4092→4078[3_1|1]
4092→4083[3_1|1]
4093→4094[5_1|1]
4094→4095[1_1|1]
4095→4096[3_1|1]
4096→4097[0_1|1]
4097→4062[5_1|1]
4097→4078[5_1|1]
4097→4083[5_1|1]
4098→4099[5_1|1]
4099→4100[1_1|1]
4100→4064[3_1|1]
4100→4101[3_1|1]
4100→4115[3_1|1]
4100→4120[3_1|1]
4100→4089[3_1|1]
4100→4094[3_1|1]
4100→4099[3_1|1]
4100→4106[3_1|1]
4101→4102[3_1|1]
4102→4103[1_1|1]
4103→4104[3_1|1]
4104→4064[1_1|1]
4104→4101[1_1|1]
4104→4115[1_1|1]
4104→4120[1_1|1]
4104→4089[1_1|1]
4104→4094[1_1|1]
4104→4099[1_1|1]
4104→4106[1_1|1]
4105→4106[5_1|1]
4106→4107[3_1|1]
4107→4108[3_1|1]
4108→4109[3_1|1]
4109→4064[1_1|1]
4109→4101[1_1|1]
4109→4115[1_1|1]
4109→4120[1_1|1]
4109→4089[1_1|1]
4109→4094[1_1|1]
4109→4099[1_1|1]
4109→4106[1_1|1]
4110→4111[1_1|1]
4111→4112[5_1|1]
4112→4113[5_1|1]
4113→4114[3_1|1]
4114→4064[1_1|1]
4114→4101[1_1|1]
4114→4115[1_1|1]
4114→4120[1_1|1]
4114→4089[1_1|1]
4114→4094[1_1|1]
4114→4099[1_1|1]
4114→4106[1_1|1]
4115→4116[1_1|1]
4116→4117[3_1|1]
4117→4118[1_1|1]
4118→4119[3_1|1]
4119→4064[5_1|1]
4119→4101[5_1|1]
4119→4115[5_1|1]
4119→4120[5_1|1]
4120→4121[4_1|1]
4121→4122[1_1|1]
4122→4123[4_1|1]
4123→4124[1_1|1]
4124→4064[5_1|1]
4124→4101[5_1|1]
4124→4115[5_1|1]
4124→4120[5_1|1]
4125→4126[2_1|1]
4126→4127[5_1|1]
4127→4128[3_1|1]
4128→4129[4_1|1]
4129→4064[1_1|1]
4129→4101[1_1|1]
4129→4115[1_1|1]
4129→4120[1_1|1]

(2) BOUNDS(O(1), O(n^1))